package com.cqs.leetcode.tree;

import com.cqs.leetcode.TreeNode;

/**
 * lixw
 * 2021/11/4
 **/
public class PathSumIII437 {

    private int cnt = 0;

    public int pathSum(TreeNode root, int targetSum) {
        dfsPathSum(root,targetSum);
        return cnt;
    }

    private void dfsPathSum(TreeNode root, int targetSum){
        if (root == null) {
            return;
        }
        dfs(root,0,targetSum);
        dfsPathSum(root.left,targetSum);
        dfsPathSum(root.right,targetSum);
    }

    private int dfs(TreeNode root, int sum, int target) {
        if (root == null) {
            return 0;
        }
        sum += root.val;
        if (sum == target) {
            ++cnt;
        }
        dfs(root.left, sum, target);
        dfs(root.right, sum, target);
        return sum;
    }
}
